package quadtree.point;

import java.awt.Dimension;
import java.awt.Point;
import java.util.HashMap;
import java.util.Map;
import java.util.Vector;

import quadtree.AbstractNode;

public class PointNode<T> extends AbstractNode {

	

	public Map<Cell, PointNode<T>> nodes = new HashMap<Cell, PointNode<T>>();
	public PointNode<T> parent = null;

	/**
	 * Holds all elements for this node
	 */
	protected Vector<PointNodeElement<T>> elements = new Vector<PointNodeElement<T>>();

	public PointNode(Point startCoordinates, Dimension bounds, int depth) {
		super(startCoordinates, bounds, depth);
		
	}

	/**
	 * 
	 * @param startCoordinates
	 * @param bounds
	 * @param depth
	 * @param maxDepth
	 * @param maxChildren
	 */
	public PointNode(Point startCoordinates, Dimension bounds, int depth,
			int maxDepth, int maxChildren, PointNode<T> parent) {
		super(startCoordinates, bounds, depth, maxDepth, maxChildren);
		this.parent = parent;
	}

	/**
	 * Returns the subnodes of this node
	 * 
	 * @return
	 */
	public Map<Cell, PointNode<T>> getSubNodes() {
		return this.nodes;
	}

	/**
	 * Returns the cell of this element
	 * 
	 * @param element
	 * @return
	 */
	protected Cell findIndex(Point coordinates) {
		// Compute the sector for the coordinates
		boolean left = (coordinates.x >= (startCoordinates.x + bounds.width / 2)) ? false
				: true;
		boolean top = (coordinates.y >= (startCoordinates.y + bounds.height / 2)) ? false
				: true;

		// top left
		Cell index = Cell.TOP_LEFT;
		if (left) {
			// left side
			if (!top) {
				// bottom left
				index = Cell.BOTTOM_LEFT;
			}
		} else {
			// right side
			if (top) {
				// top right
				index = Cell.TOP_RIGHT;
			} else {
				// bottom right
				index = Cell.BOTTOM_RIGHT;

			}
		}
		
		return index;
	}

	/**
	 * Returns all elements for this node
	 * 
	 * @return
	 */
	public Vector<PointNodeElement<T>> getElements() {
		return this.elements;
	}

	/**
	 * Returns all elements within the cell that matches the given coordinates
	 * 
	 * @param coordinates
	 * @return
	 */
	public Vector<PointNodeElement<T>> getElements(Point coordinates) {

		// Check if this node has already been subdivided. Therefore this node
		// should contain no elements
		if (nodes.size() > 0) {
			Cell index = findIndex(coordinates);
			PointNode<T> node = this.nodes.get(index);
			return node.getElements(coordinates);
		} else {
			return this.elements;
		}
	}
	
	public PointNodeElement<T> getElement(Point coordinates, T element) {
		if(nodes.size() > 0) {
			Cell index = findIndex(coordinates);
			PointNode<T> node = this.nodes.get(index);
			return node.getElement(coordinates, element);
		}
		else {
			for(int i = 0; i < elements.size(); i++) {
				if(element.equals(elements.get(i))) {
					return elements.get(i);
				}
			}
			return null;
		}
	}
	
	public boolean removeElement(Point coordinates, T element) {
		if(nodes.size() > 0) {
			Cell index = findIndex(coordinates);
			PointNode<T> node = this.nodes.get(index);
			return node.removeElement(coordinates, element); 
		}
		else {
			for(int i = 0; i < elements.size(); i++) {
				if(element == elements.get(i)) {
					elements.remove(i);
				}
			}
			/*if(elements.size() == 0) {
				if(parent.nodes.get(Cell.TOP_LEFT).elements.size()==0) {
					if (parent.nodes.get(Cell.BOTTOM_LEFT).elements.size() == 0) {
						if (parent.nodes.get(Cell.BOTTOM_RIGHT).elements.size() == 0) {
							if (parent.nodes.get(Cell.TOP_RIGHT).elements.size() == 0) {
								parent.nodes = new HashMap<Cell, PointNode<T>>();
								return true;
							}
						}
					}
				}
			}*/
			return false;
		}
	}

	/**
	 * Insert the element into this node. If needed a subdivision will be
	 * performed
	 * 
	 * @param element
	 */
	public void insert(PointNodeElement<T> element) {
		
		// If this Node has already been subdivided just add the elements to the
		// appropriate cell
		if (this.nodes.size() != 0) {
			Cell index = findIndex(element);
			//elements.add(element);
			
			this.nodes.get(index).insert(element);
			return;
		}

		// Add the element to this node and to parent
		/*if(parent != null) {
			//signifies root node doesnt have a parent
			parent.elements.add(element);
		}*/
		this.elements.add(element);

		// Only subdivide the node if it contain more than MAX_CHILDREN and is
		// not the deepest node
		if (!(this.depth >= maxDepth) && this.elements.size() > maxElements) {
			this.subdivide();

			// Recall insert for each element. This will move all elements of
			// this node into the new nodes at the appropriate cell
			for (int i = 0; i < elements.size(); i++) {
				PointNodeElement<T> current = elements.get(i);
				this.insert(current);
			}
			// Remove all elements from this node since they were moved into
			// subnodes
			this.elements.clear();
		}
	}
	
	public void preDivide() {
		if (!(this.depth >= maxDepth)) {
			this.subdivide();
			nodes.get(Cell.BOTTOM_LEFT).preDivide();
			nodes.get(Cell.TOP_LEFT).preDivide();
			nodes.get(Cell.BOTTOM_RIGHT).preDivide();
			nodes.get(Cell.TOP_RIGHT).preDivide();
		}
	}
	
	public Vector<PointNodeElement<T>> queryObject(Point coordinates, Dimension size) {
		if(nodes.size() == 0) {
			return elements;
		}
		else {
			PointNode<T> topLeftNode = nodes.get(Cell.TOP_LEFT);
			PointNode<T> bottomLeftNode = nodes.get(Cell.BOTTOM_LEFT);
			PointNode<T> bottomRightNode = nodes.get(Cell.BOTTOM_RIGHT);
			PointNode<T> topRightNode = nodes.get(Cell.TOP_RIGHT);
			Vector<PointNodeElement<T>> TopLeft = null;
			Vector<PointNodeElement<T>> BottomLeft = null;
			Vector<PointNodeElement<T>> BottomRight = null;
			Vector<PointNodeElement<T>> TopRight = null;
			Vector<PointNodeElement<T>> master = new Vector<PointNodeElement<T>>();
			if(topLeftNode.startCoordinates.x + topLeftNode.bounds.width >= coordinates.x
					&& topLeftNode.startCoordinates.y + topLeftNode.bounds.height >= coordinates.y) {
				//System.out.println("topLeft " + (topLeftNode.startCoordinates.x + topLeftNode.bounds.width) + " >= " + coordinates.x);
				TopLeft = topLeftNode.queryObject(coordinates, size);
			}
			if(topRightNode.startCoordinates.x <= coordinates.x + size.width
					&& topRightNode.startCoordinates.y + topRightNode.bounds.height >= coordinates.y) {
				//System.out.println("topRight " + topRightNode.startCoordinates.x + " <= " + (coordinates.x + size.width));
				TopRight = topRightNode.queryObject(coordinates, size);
			}
			if(bottomLeftNode.startCoordinates.y <= coordinates.y + size.height
					&& bottomLeftNode.startCoordinates.x + bottomLeftNode.bounds.width >= coordinates.x) {
				//System.out.println("bottomLeft " + bottomLeftNode.startCoordinates.y + " <= " + (coordinates.y + size.height));
				BottomLeft = bottomLeftNode.queryObject(coordinates, size);
			}
			if(bottomRightNode.startCoordinates.x <= coordinates.x + size.width
					&& bottomRightNode.startCoordinates.y <= coordinates.y + size.height) {
				//System.out.println("bottomRight " + bottomRightNode.startCoordinates.x + " <= " + (coordinates.x + size.width)
				//+ " && " + bottomRightNode.startCoordinates.y + " <= " + (coordinates.x + size.height));
				BottomRight = bottomRightNode.queryObject(coordinates, size);
			}
			if(TopLeft != null) {
				master.addAll(TopLeft);
			}
			if(BottomLeft != null) {
				master.addAll(BottomLeft);
			}
			if(BottomRight != null) {
				master.addAll(BottomRight);
			}
			if(TopRight != null) {
				master.addAll(TopRight);
			}
			return master;
		}
			
	}

	/**
	 * Subdivide the current node and add subnodes
	 */
	public void subdivide() {
		
		int depth = this.depth + 1;

		int bx = this.startCoordinates.x;
		int by = this.startCoordinates.y;

		// Create the bounds for the new cell
		Dimension newBounds = new Dimension(this.bounds.width / 2,
				this.bounds.height / 2);

		// Add new bounds to current start coordinates to calculate the new
		// start coordinates
		int newXStartCoordinate = bx + newBounds.width;
		int newYStartCoordinate = by + newBounds.height;

		PointNode<T> cellNode = null;

		// top left
		cellNode = new PointNode<T>(new Point(bx, by), newBounds, depth,
				this.maxDepth, this.maxElements, this);
		this.nodes.put(Cell.TOP_LEFT, cellNode);

		// top right
		cellNode = new PointNode<T>(new Point(newXStartCoordinate, by),
				newBounds, depth, this.maxDepth, this.maxElements, this);
		this.nodes.put(Cell.TOP_RIGHT, cellNode);

		// bottom left
		cellNode = new PointNode<T>(new Point(bx, newYStartCoordinate),
				newBounds, depth, this.maxDepth, this.maxElements, this);
		this.nodes.put(Cell.BOTTOM_LEFT, cellNode);

		// bottom right
		cellNode = new PointNode<T>(new Point(newXStartCoordinate,
				newYStartCoordinate), newBounds, depth, this.maxDepth,
				this.maxElements, this);
		this.nodes.put(Cell.BOTTOM_RIGHT, cellNode);
	}

	/**
	 * Clears this node and all subnodes
	 */
	public void clear() {
		for (PointNode<T> node : nodes.values()) {
			node.clear();
		}
		elements.clear();
		nodes.clear();
	}
}
